package main

import (
	"math"
)

func maximumSum2(arr []int) int {
	max := math.MinInt
	dpMin := make([][]int, len(arr))
	dpSum := make([][]int, len(arr))
	for i := 0; i < len(arr); i++ {
		dpMin[i] = make([]int, len(arr))
		dpSum[i] = make([]int, len(arr))
	}

	for i := 0; i < len(arr); i++ {
		dpMin[i][i] = arr[i]
		dpSum[i][i] = arr[i]
	}

	min := func(a, b int) int {
		if a > b {
			return b
		}

		return a
	}

	for i := 0; i < len(dpSum); i++ {
		for j := i; j < len(dpSum); j++ {
			if j-i == 0 {
				continue
			}
			dpSum[i][j] = dpSum[i][j-1] + arr[j]
		}
	}

	for i := 0; i < len(dpMin); i++ {
		for j := i; j < len(dpMin[0]); j++ {
			if j-i == 0 {
				continue
			}
			dpMin[i][j] = min(dpMin[i][j-1], arr[j])
		}
	}

	for i := 0; i < len(arr); i++ {
		for j := i; j < len(arr); j++ {
			if j-i == 0 {
				if max < dpSum[i][j] {
					max = dpSum[i][j]
				}
				continue
			}

			if dpMin[i][j] < 0 {
				temp := dpSum[i][j]

				if max < temp-dpMin[i][j] {
					max = temp - dpMin[i][j]
				}

			} else {
				if max < dpSum[i][j] {
					max = dpSum[i][j]
				}
			}
		}
	}

	return max
}

func maximumSum(arr []int) int {
	max := math.MinInt
	dpTailSum := make([]int, len(arr))
	dpTailSum[0] = arr[0]

	dpMin := make([]int, len(arr))
	dpMin[0] = arr[0]
	min := func(a, b int) int {
		if a > b {
			return b
		}

		return a
	}

	for i := 1; i < len(arr); i++ {
		dpMin[i] = min(dpMin[i-1], arr[i])
	}

	for i := 1; i < len(arr); i++ {
		if arr[i] > 0 {
			dpTailSum[i] = dpTailSum[i-1] + arr[i]
		} else {
			dpTailSum[i] = dpTailSum[i-1]
		}

		if dpMin[i] < 0 && dpTailSum[i] != arr[i] {
			if max < dpTailSum[i]-dpMin[i] {
				max = dpTailSum[i] - dpMin[i]
			}
		}

	}

	return max
}
func main() {
	maximumSum([]int{1, -2, 0, 3})
}
